#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

/*****定义结构体*****/
struct btnode
{
    char data;
    struct btnode *lc, *rc;
}; //*btnode, *btree;
typedef struct btnode btnode;
typedef struct btnode *btree;
/*****定义结构体*****/

void bt2ie_temp(btree root, int depth)
{
    if (root == NULL)
    {
        printf("二叉树为空！\n"); //根结点为空，说明是个空树
    }
    else if (root->lc == NULL && root->rc == NULL) //叶子结点均为操作数
    {
        printf("%c", root->data); //输出操作数（不需要加括号）
    }
    else
    {
        if (depth > 1 && root->data != '*' && root->data != '/')
        {
            printf("("); //还有子表达式，要加括号
        }
        bt2ie_temp(root->lc, depth + 1); //递归调用遍历左边
        printf("%c", root->data);
        bt2ie_temp(root->rc, depth + 1);
        if (depth > 1 && root->data != '*' && root->data != '/')
        {
            printf(")");
        }
    }
}

void bt2ie(btree root) // infix expression
{
    bt2ie_temp(root, 1); //根结点的高度为1
}

/*****声明二叉树结点*****/
btree t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11;
/*****声明二叉树结点*****/

/*****初始化二叉树*****/
void t_init()
{
    t1->lc = nullptr;
    t1->rc = nullptr;
    t2->lc = nullptr;
    t2->rc = nullptr;
    t3->lc = nullptr;
    t3->rc = nullptr;
    t4->lc = nullptr;
    t4->rc = nullptr;
    t5->lc = nullptr;
    t5->rc = nullptr;
    t6->lc = nullptr;
    t6->rc = nullptr;
    t7->lc = nullptr;
    t7->rc = nullptr;
    t8->lc = nullptr;
    t8->rc = nullptr;
    t9->lc = nullptr;
    t9->rc = nullptr;
    t10->lc = nullptr;
    t10->rc = nullptr;
    t11->lc = nullptr;
    t11->rc = nullptr;
}
/*****初始化二叉树*****/

int main()
{
    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));
    t9 = (btree)malloc(sizeof(btnode));
    t10 = (btree)malloc(sizeof(btnode));
    t11 = (btree)malloc(sizeof(btnode));

    t_init();
    t1->data = '-';
    t1->lc = t2;
    t1->rc = t3;
    t2->data = '+';
    t2->lc = t4;
    t2->rc = t5;
    t3->data = '/';
    t3->lc = t6;
    t3->rc = t7;
    t4->data = 'a';
    t5->data = '*';
    t5->lc = t8;
    t5->rc = t9;
    t6->data = 'e';
    t7->data = 'f';
    t8->data = 'b';
    t9->data = '-';
    t9->lc = t10;
    t9->rc = t11;
    t10->data = 'c';
    t11->data = 'd';
    bt2ie(t1);
    printf("\n");

    system("pause");
}